package Demo3;

public class Practice {
    //归并排序
    public static void mergerSort(int[] arr){
        mergerSortFunc(arr,0,arr.length-1);
    }
    //递归分解
    private  static void  mergerSortFunc(int[] arr,int left,int right) {
        if (left>=right){
            return;
        }
        int mid = (left + right)/2;
        mergerSortFunc(arr,left,mid);
        mergerSortFunc(arr,mid+1,right);
        merge(arr,left,right,mid);
    }
    //合并
    private static void merge(int[] arr,int start,int end,int mid){
        int s1=start;
        int s2=mid+1;
        int[] tmp=new int[end-start+1];
        int k=0;//tmp数组下标
        //分解后的两个数组，两边都有数据的情况才做
        while (s1<=mid && s2<=end){
            //交换
            if (arr[s1]<=arr[s2]){
                tmp[k++]=arr[s1++];
            }else {
                tmp[k++]=arr[s2++];
            }
        }
        //检查某一边是是否还有剩余元素
        while (s1<=mid){//说明左边还有元素
            tmp[k++]=arr[s1++];
        }
        while (s2<=end){//说明右边还有元素
            tmp[k++]=arr[s2++];
        }
        //将tmp数组写到原来的数组
        for (int i=0;i<end;i++){
            arr[i+start]=tmp[i];//由于需要入值的下标可能不是从0开始，所有i需要加上开始下标
        }
    }

}
